package 动态规划;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @description:
 * @author: ywk
 * @date: 2021-04-01
 */
public class 最长公共前缀 {
    public static String longestCommonPrefix(String[] strs) {
        // write code here
        Arrays.sort(strs, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length() - o2.length();
            }
        });
        int start = 0;
        int end = 0;
        out:
        for (int j = 0; j < strs[0].length(); j++) {
            char c = strs[0].charAt(j);
            for (int i = 1; i < strs.length; i++) {
                String str = strs[i];
                if (c != str.charAt(j)) {
                    break out;
                }
            }
            end++;
        }
        return strs[0].substring(start, end);

    }

    public static void main(String[] args) {
        System.out.println(longestCommonPrefix(new String[]{"abca", "abc", "abca", "abc", "abcc"}));
    }
}
